package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.Arrays;
import java.util.Collections;

/**
 * @author Fengkai
 * @creat 2023/4/18
 * 【租车骑绿岛】100分
 * 部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，做最大载重M。
 * 给出部门每个人的体重，请问最多需要租用多少双人自行车。
 * 输入描述：
 * 第一行两个数字m、n，分别代表自行车限重，部门总人数。
 * 第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。
 * 0<m<=200
 * 0<n<=1000000
 * 输出描述：
 * 最小需要的双人自行车数量。
 * 示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
 */
public class MinBikes {
    public static void main (String[] args) {
        System.out.println(getMinBikes(3, new int[]{3, 2, 2, 1}));
    }

    public static int getMinBikes (int m, int weights[]) {
        int count = 0;
        Arrays.sort(weights);
        int letf = 0, right = weights.length - 1;
        while (letf <= right) {
            if (letf == right) {
                count++;
                break;
            }
            if (weights[right] >= m) {
                count++;
                right--;
                continue;
            } else if (weights[right] + weights[letf] <= m) {
                count++;
                letf++;
                right--;
                continue;
            } else if (weights[right] + weights[letf] > m) {
                right--;
                count++;
            }

        }
        return count;
    }
}
